branch prediction

processor, algorithm A technique used in some processors

with instruction prefetch to guess whether a conditionalbranch will be taken or not and prefetch code from the

appropriate location.

When a branch instruction is executed, its address and that of

the next instruction executed (the chosen destination of the

branch) are stored in the Branch Target Buffer. This

information is used to predict which way the instruction will

branch the next time it is executed so that instruction

prefetch can continue. When the prediction is correct (and it

is over 90% of the time), executing a branch does not cause a

pipeline break.

Some later CPUs simply prefetch both paths instead of trying

to predict which way the branch will go.

An extension of the idea of branch prediction is speculativeexecution.

(1998-03-14)